## Рекурсии и сортировки

<details>
<summary>
<strong>Генератор скобок</strong>
</summary><br>

[`Решение`](/sprint_3/1_bracketGenerator.js) | [`Условие`](https://contest.yandex.ru/contest/23638/problems/A/) | [`Отчет`](https://contest.yandex.ru/contest/23638/run-report/108399729/)
```
Рита по поручению Тимофея наводит порядок в правильных скобочных последовательностях (ПСП), состоящих только из круглых скобок (). Для этого ей надо сгенерировать все ПСП длины 2n в алфавитном порядке —– алфавит состоит из ( и ) и открывающая скобка идёт раньше закрывающей.
Помогите Рите —– напишите программу, которая по заданному n выведет все ПСП в нужном порядке.
Рассмотрим второй пример. Надо вывести ПСП из четырёх символов. Таких всего две:
1. (())
2. ()()
(()) идёт раньше ()(), так как первый символ у них одинаковый, а на второй позиции у первой ПСП стоит (, который идёт раньше ).
```
#### Формат ввода
```
На вход функция принимает n — целое число от 0 до 10.
```
#### Формат вывода
```
Функция должна напечатать все возможные скобочные последовательности заданной длины в алфавитном (лексикографическом) порядке.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        3<br>
    </td>
    <td valign="top">
        ((()))<br>
        (()())<br>
        (())()<br>
        ()(())<br>
        ()()()<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Комбинации</strong>
</summary><br>

[`Решение`](/sprint_3/2_combinations.js) | [`Условие`](https://contest.yandex.ru/contest/23638/problems/B/) | [`Отчет`](https://contest.yandex.ru/contest/23638/run-report/108482642/)
```
На клавиатуре старых мобильных телефонов каждой цифре соответствовало несколько букв. Примерно так:

2:'abc',
3:'def',
4:'ghi',
5:'jkl',
6:'mno',
7:'pqrs',
8:'tuv',
9:'wxyz'

Вам известно в каком порядке были нажаты кнопки телефона, без учета повторов. Напечатайте все комбинации букв, которые можно набрать такой последовательностью нажатий.
```
#### Формат ввода
```
На вход подается строка, состоящая из цифр 2-9 включительно. Длина строки не превосходит 10 символов.
```
#### Формат вывода
```
Выведите все возможные комбинации букв через пробел.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        23<br>
    </td>
    <td valign="top">
        ad ae af bd be bf cd ce cf<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Подпоследовательность</strong>
</summary>

[`Условие`](https://contest.yandex.ru/contest/24734/problems/C/)
```
Гоша любит играть в игру «Подпоследовательность»: даны 2 строки, и нужно понять, 
является ли первая из них подпоследовательностью второй. Когда строки достаточно 
длинные, очень трудно получить ответ на этот вопрос, просто посмотрев на них. 
Помогите Гоше написать функцию, которая решает эту задачу.
```
#### Формат ввода
```
В первой строке записана строка s.
Во второй —- строка t.
Обе строки состоят из маленьких латинских букв, длины строк не превосходят 150000. 
Строки не могут быть пустыми.
```
#### Формат вывода
```
Выведите True, если s является подпоследовательностью t, иначе —– False.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        abc<br>
        ahbgdcu<br>
    </td>
    <td valign="top">
        True<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Печеньки</strong>
</summary><br>

[`Решение`](/sprint_3/4_cookies.js) | [`Условие`](https://contest.yandex.ru/contest/24734/problems/D/) | [`Отчет`](https://contest.yandex.ru/contest/23638/run-report/114212548/)
```
К Васе в гости пришли одноклассники. Его мама решила угостить ребят печеньем.
Но не всё так просто. Печенья могут быть разного размера. А у каждого ребёнка есть фактор жадности —– минимальный размер печенья, которое он возьмёт. Нужно выяснить, сколько ребят останутся довольными в лучшем случае, когда они действуют оптимально.
Каждый ребёнок может взять не больше одного печенья.
```
#### Формат ввода
```
В первой строке записано n —– количество детей.
Во второй —– n чисел, разделённых пробелом, каждое из которых –— фактор жадности ребёнка. Это натуральные числа, не превосходящие 1000.
В следующей строке записано число m –— количество печенек.
Далее —– m натуральных чисел, разделённых пробелом —– размеры печенек. Размеры печенек не превосходят 1000.
Оба числа n и m не превосходят 10000.
```
#### Формат вывода
```
Нужно вывести одно число –— количество детей, которые останутся довольными
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        2<br>
        1 2<br>
        3<br>
        2 1 3<br>
    </td>
    <td valign="top">
        2<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Покупка домов</strong>
</summary><br>

[`Условие`](https://contest.yandex.ru/contest/24734/problems/E/)
```
Тимофей решил купить несколько домов на знаменитом среди разработчиков Алгосском архипелаге. 
Он нашёл n объявлений о продаже, где указана стоимость каждого дома в алгосских франках. 
А у Тимофея есть k франков. Помогите ему определить, какое наибольшее количество домов на Алгосах он сможет приобрести за эти деньги.
```
#### Формат ввода
```
В первой строке через пробел записаны натуральные числа n и k.
n — количество домов, которые рассматривает Тимофей, оно не превосходит 100000;
k — общий бюджет, не превосходит 100000;
В следующей строке через пробел записано n стоимостей домов. 
Каждое из чисел не превосходит 100000. Все стоимости — натуральные числа.
```
#### Формат вывода
```
Выведите одно число —– наибольшее количество домов, которое может купить Тимофей.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        3 300<br>
        999 999 999<br>
    </td>
    <td valign="top">
        0<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Периметр треугольника</strong>
</summary><br>

[`Условие`](https://contest.yandex.ru/contest/24734/problems/F/)
```
Перед сном Рита решила поиграть в игру на телефоне. Дан массив целых чисел, в котором каждый элемент обозначает длину стороны треугольника. Нужно определить максимально возможный периметр треугольника, составленного из сторон с длинами из заданного массива. Помогите Рите скорее закончить игру и пойти спать.
Напомним, что из трёх отрезков с длинами a ≤ b ≤ c можно составить треугольник, если выполнено **неравенство треугольника**: c < a + b
Разберём пример:
даны длины сторон 6, 3, 3, 2. Попробуем в качестве наибольшей стороны выбрать 6. Неравенство треугольника не может выполниться, так как остались 3, 3, 2 —– максимальная сумма из них равна 6.
Без шестёрки оставшиеся три отрезка уже образуют треугольник со сторонами 3, 3, 2. Неравенство выполняется: 3 < 3 + 2. Периметр равен 3 + 3 + 2 = 8.
```
#### Формат ввода
```
В первой строке записано количество отрезков n, 3≤ n≤ 10000.
Во второй строке записано n неотрицательных чисел, не превосходящих 10 000, –— длины отрезков.
```
#### Формат вывода
```
Нужно вывести одно число —– наибольший периметр треугольника.
Гарантируется, что тройка чисел, которая может образовать треугольник, всегда есть.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        4<br>
        6 3 3 2<br>
    </td>
    <td valign="top">
        8<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Гардероб</strong>
</summary><br>

[`Решение`](/sprint_3/7_wardrobe.js) | [`Условие`](https://contest.yandex.ru/contest/24734/problems/G/) | [`Отчет`](https://contest.yandex.ru/contest/23638/run-report/114210103/)
```
Рита решила оставить у себя одежду только трёх цветов: розового, жёлтого и малинового. После того как вещи других расцветок были убраны, Рита захотела отсортировать свой новый гардероб по цветам. Сначала должны идти вещи розового цвета, потом —– жёлтого, и в конце —– малинового. Помогите Рите справиться с этой задачей.
Примечание: попробуйте решить задачу за один проход по массиву!
```
#### Формат ввода
```
В первой строке задано количество предметов в гардеробе: n –— оно не превосходит 1000000. 
Во второй строке даётся массив, в котором указан цвет для каждого предмета. Розовый цвет обозначен 0, жёлтый —– 1, малиновый –— 2.
```
#### Формат вывода
```
Нужно вывести в строку через пробел цвета предметов в правильном порядке.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        7<br>
        0 2 1 2 0 0 1<br>
    </td>
    <td valign="top">
        0 0 0 1 1 2 2<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Большое число</strong>
</summary><br>

[`Решение`](/sprint_3/8_bigCount.js) | [`Условие`](https://contest.yandex.ru/contest/24734/problems/H/) | [`Отчет`](https://contest.yandex.ru/contest/23638/run-report/108948562/)
```
Вечером ребята решили поиграть в игру «Большое число».
Даны числа. Нужно определить, какое самое большое число можно из них составить.
```
#### Формат ввода
```
В первой строке записано n — количество чисел. Оно не превосходит 100.
Во второй строке через пробел записаны n неотрицательных чисел, каждое из которых не превосходит 1000.
```
#### Формат вывода
```
Нужно вывести самое большое число, которое можно составить из данных чисел.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        3<br>
        15 56 2<br>
    </td>
    <td valign="top">
        56215<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Любители конференций</strong>
</summary><br>

[`Решение`](/sprint_3/9_conferenceLovers.js) | [`Условие`](https://contest.yandex.ru/contest/24734/problems/I/) | [`Отчет`](https://contest.yandex.ru/contest/23638/run-report/114154666/)
```
На IT-конференции присутствовали студенты из разных вузов со всей страны. Для каждого студента известен ID университета, в котором он учится.
Тимофей предложил Рите выяснить, из каких k вузов на конференцию пришло больше всего учащихся.
```
#### Формат ввода
```
В первой строке дано количество студентов в списке —– n (1 ≤ n ≤ 15 000).
Во второй строке через пробел записаны n целых чисел —– ID вуза каждого студента. Каждое из чисел находится в диапазоне от 0 до 10 000.
В третьей строке записано одно число k.
```
#### Формат вывода
```
Выведите через пробел k ID вузов с максимальным числом участников. 
Они должны быть отсортированы по убыванию популярности (по количеству гостей от конкретного вуза). 
Если более одного вуза имеет одно и то же количество учащихся, то выводить их ID нужно в порядке возрастания.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        7<br>
        1 2 3 1 2 3 4<br>
        3<br>
    </td>
    <td valign="top">
        1 2 3<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Пузырёк</strong>
</summary><br>

[`Решение`](/sprint_3/10_bubble.js) | [`Условие`](https://contest.yandex.ru/contest/24734/problems/J/) | [`Отчет`](https://contest.yandex.ru/contest/23638/run-report/108944666/)
```
Чтобы выбрать самый лучший алгоритм для решения задачи, Гоша продолжил изучать разные сортировки. На очереди сортировка пузырьком — https://ru.wikipedia.org/wiki/Сортировка_пузырьком
Её алгоритм следующий (сортируем по неубыванию):
1. На каждой итерации проходим по массиву, поочередно сравнивая пары соседних элементов. Если элемент на позиции i больше элемента на позиции i + 1, меняем их местами. После первой итерации самый большой элемент всплывёт в конце массива.
2. Проходим по массиву, выполняя указанные действия до тех пор, пока на очередной итерации не окажется, что обмены больше не нужны, то есть массив уже отсортирован.
3. После не более чем n – 1 итераций выполнение алгоритма заканчивается, так как на каждой итерации хотя бы один элемент оказывается на правильной позиции.

Помогите Гоше написать код алгоритма.
```
#### Формат ввода
```
В первой строке на вход подаётся натуральное число n — длина массива, 2 ≤ n ≤ 1000.
Во второй строке через пробел записано n целых чисел.
Каждое из чисел по модулю не превосходит 1000.

Обратите внимание, что считывать нужно только 2 строки: значение n и входной массив.
```
#### Формат вывода
```
После каждого прохода по массиву, на котором какие-то элементы меняются местами, выводите его промежуточное состояние.
Таким образом, если сортировка завершена за k меняющих массив итераций, то надо вывести k строк по n чисел в каждой — элементы массива после каждой из итераций.
Если массив был изначально отсортирован, то просто выведите его.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        5<br>
        4 3 9 2 1<br>
    </td>
    <td valign="top">
        3 4 2 1 9<br>
        3 2 1 4 9<br>
        2 1 3 4 9<br>
        1 2 3 4 9<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Сортировка слиянием</strong>
</summary><br>

[`Решение`](/sprint_3/11_mergeSort.js) | [`Условие`](https://contest.yandex.ru/contest/24734/problems/K/) | [`Отчет`](https://contest.yandex.ru/contest/23638/run-report/114207642/)
```
Гоше дали задание написать красивую сортировку слиянием. Поэтому Гоше обязательно надо реализовать отдельно функцию merge и функцию merge_sort.
Функция merge принимает два отсортированных массива, сливает их в один отсортированный массив и возвращает его. Если требуемая сигнатура имеет вид merge(array, left, mid, right), то первый массив задаётся полуинтервалом 
[left,mid) массива array, а второй – полуинтервалом [mid,right) массива array.
Функция merge_sort принимает некоторый подмассив, который нужно отсортировать. Подмассив задаётся полуинтервалом — его началом и концом. Функция должна отсортировать передаваемый в неё подмассив, она ничего не возвращает.
Функция merge_sort разбивает полуинтервал на две половинки и рекурсивно вызывает сортировку отдельно для каждой. Затем два отсортированных массива сливаются в один с помощью merge.
Заметьте, что в функции передаются именно полуинтервалы [begin,end), то есть правый конец не включается. Например, если вызвать merge_sort(arr, 0, 4), где 
arr=`[4,5,3,0,1,2]`, то будут отсортированы только первые четыре элемента, изменённый массив будет выглядеть как 
arr=`[0,3,4,5,1,2]`.
Реализуйте эти две функции.
```
#### Формат ввода
```
Передаваемый в функции массив состоит из целых чисел, не превосходящих по модулю 
10^9. Длина сортируемого диапазона не превосходит 10^5.
```
#### Формат вывода
```
При написании и отправке решений соблюдайте следующие правила:

`merge(arr: list, left: int, mid: int, right: int) -> array` 
`merge_sort(arr: list, left: int, right: int) -> None`
```
</details>

---

<details>
<summary>
<strong>Два велосипеда</strong>
</summary><br>

[`Решение`](/sprint_3/12_twoBycicles.js) | [`Условие`](https://contest.yandex.ru/contest/24734/problems/L/) | [`Отчет`](https://contest.yandex.ru/contest/23638/run-report/108383165/)
```
Вася решил накопить денег на два одинаковых велосипеда — себе и сестре. У Васи есть копилка, в которую каждый день он может добавлять деньги (если, конечно, у него есть такая финансовая возможность). В процессе накопления Вася не вынимает деньги из копилки.
У вас есть информация о росте Васиных накоплений — сколько у Васи в копилке было денег в каждый из дней.
Ваша задача — по заданной стоимости велосипеда определить

 - первый день, в которой Вася смог бы купить один велосипед,
 - и первый день, в который Вася смог бы купить два велосипеда.
**Подсказка:** решение должно работать за O(log n).
```
#### Формат ввода
```
В первой строке дано число дней n, по которым велись наблюдения за Васиными накоплениями. 1 ≤ n ≤ 10^6.
В следующей строке записаны n целых неотрицательных чисел. Числа идут в порядке неубывания. Каждое из чисел не превосходит 10^6.
В третьей строке записано целое положительное число s — стоимость велосипеда. Это число не превосходит 10^6.
```
#### Формат вывода
```
Нужно вывести два числа — номера дней по условию задачи.
Если необходимой суммы в копилке не нашлось, нужно вернуть -1 вместо номера дня.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        6<br>
        1 2 4 4 6 8<br>
        3<br>
    </td>
    <td valign="top">
        3 5<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Золотая середина</strong>
</summary><br>

[`Решение`](/sprint_3/13_goldenMiddle.js) | [`Условие`](https://contest.yandex.ru/contest/24734/problems/M/) | [`Отчет`](https://contest.yandex.ru/contest/23638/run-report/114159785/)
```
Задача повышенной сложности

На каждом острове в архипелаге Алгосы живёт какое-то количество людей или же остров необитаем (тогда на острове живёт 0 людей).
Пусть на i-м острове численность населения составляет ai. Тимофей захотел найти медиану среди всех значений численности населения.

Определение: Медиана (https://ru.wikipedia.org/wiki/Медиана_(статистика)) массива чисел a_i —– это такое число,
что половина чисел из массива не больше него, а другая половина не меньше. В общем случае медиану массива можно найти,
отсортировав числа и взяв среднее из них. Если количество чисел чётно, то возьмём в качестве медианы полусумму соседних
средних чисел, (a[n/2] + a[n/2 + 1])/2.

У Тимофея уже есть отдельно данные по северной части архипелага и по южной,
причём значения численности населения в каждой группе отсортированы по неубыванию.

Определите медианную численность населения по всем островам Алгосов.

Подсказка: Если n –— число островов в северной части архипелага, а m –— в южной, то ваше решение должно работать за .
```
#### Формат ввода
```
В первой строке записано натуральное число n, во второй —– натуральное число m. Они не превосходят 10 000.

Далее в строку через пробел записаны n целых неотрицательных чисел, каждое
из которых не превосходит 10 000, –— значения численности населения в северной части Алгосов.

В последней строке через пробел записаны m целых неотрицательных чисел, каждое
из которых не превосходит 10 000 –— значения численности населения в южной части Алгосов.

Значения в третьей и четвёртой строках упорядочены по неубыванию.
```
#### Формат вывода
```
Нужно вывести одной число — найденную медиану.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        2<br>
        1<br>
        1 3<br>
        2<br>
    </td>
    <td valign="top">
        2<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Клумбы</strong>
</summary><br>

[`Решение`](/sprint_3/14_flowers.js) | [`Условие`](https://contest.yandex.ru/contest/24734/problems/N/) | [`Отчет`](https://contest.yandex.ru/contest/23638/run-report/114214162/)
```
Алла захотела, чтобы у неё под окном были узкие клумбы с тюльпанам. 
На схеме земельного участка клумбы обозначаются просто горизонтальными отрезками, лежащими на одной прямой. 
Для ландшафтных работ было нанято n садовников. Каждый из них обрабатывал какой-то отрезок на схеме. 
Процесс был организован не очень хорошо, иногда один и тот же отрезок или его часть могли быть обработаны сразу несколькими садовниками. 
Таким образом, отрезки, обрабатываемые двумя разными садовниками, сливаются в один. Непрерывный обработанный отрезок затем станет клумбой. 
Нужно определить границы будущих клумб.
Рассмотрим примеры.

Пример 1:
Два одинаковых отрезка `[7, 8]` и `[7, 8]` сливаются в один, но потом их накрывает отрезок `[6, 10]`. Таким образом, имеем две клумбы с координатами `[2,3]` и `[6,10]`.

Пример 2
Отрезки `[2,3]`, `[3, 4]` и `[3,4]` сольются в один отрезок `[2,4]`. Отрезок `[5,6]` ни с кем не объединяется, добавляем его в ответ.
```
#### Формат ввода
```
В первой строке задано количество садовников n. Число садовников не превосходит 100 000.
В следующих n строках через пробел записаны координаты клумб в формате: start end, где start —– координата начала, end —– координата конца. Оба числа целые, неотрицательные и не превосходят 10^7. start строго меньше, чем end.
```
#### Формат вывода
```
Нужно вывести координаты каждой из получившихся клумб в отдельных строках. Данные должны выводится в отсортированном порядке —– сначала клумбы с меньшими координатами, затем —– с большими.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        4<br>
        7 8<br>
        7 8<br>
        2 3<br>
        6 10<br>
    </td>
    <td valign="top">
        2 3<br>
        6 10<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Поиск в сломанном массиве | Финальная задача №1</strong>
</summary><br>

[`Решение`](/sprint_3/finals/taskA.js) | [`Условие`](https://contest.yandex.ru/contest/23815/problems/A/) | [`Отчет`](https://contest.yandex.ru/contest/23815/run-report/109499164/)

Алла ошиблась при копировании из одной структуры данных в другую. Она хранила массив чисел в кольцевом буфере. Массив был отсортирован по возрастанию, и в нём можно было найти элемент за логарифмическое время. Алла скопировала данные из кольцевого буфера в обычный массив, но сдвинула данные исходной отсортированной последовательности. Теперь массив не является отсортированным. Тем не менее, нужно обеспечить возможность находить в нем элемент за 
O(log n).
Можно предполагать, что в массиве только уникальные элементы.
От вас требуется реализовать функцию, осуществляющую поиск в сломанном массиве.

#### Формат ввода
Функция принимает массив натуральных чисел и искомое число 
k
. Длина массива не превосходит 10000. Элементы массива и число k не превосходят по значению 10000.
В примерах:
В первой строке записано число n –— длина массива.
Во второй строке записано положительное число k –— искомый элемент. 
Далее в строку через пробел записано n натуральных чисел – элементы массива.

#### Формат вывода
Функция должна вернуть индекс элемента, равного 
k, если такой есть в массиве (нумерация с нуля). Если элемент не найден, функция должна вернуть −1.
Изменять массив нельзя.
Для отсечения неэффективных решений ваша функция будет запускаться от 100000 до 1000000 раз.

#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        9<br>
        5<br>
        19 21 100 101 1 4 5 7 12<br>
    </td>
    <td valign="top">
        6<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Эффективная быстрая сортировка | Финальная задача №2</strong>
</summary><br>

[`Решение`](/sprint_3/finals/taskB.js) | [`Условие`](https://contest.yandex.ru/contest/23815/problems/B/) | [`Отчет`](https://contest.yandex.ru/contest/23815/run-report/109738768/)
```
Тимофей решил организовать соревнование по спортивному программированию, чтобы найти талантливых стажёров. Задачи подобраны, участники зарегистрированы, тесты написаны. Осталось придумать, как в конце соревнования будет определяться победитель.
Каждый участник имеет уникальный логин. Когда соревнование закончится, к нему будут привязаны два показателя: количество решённых задач Pi и размер штрафа Fi. Штраф начисляется за неудачные попытки и время, затраченное на задачу.
Тимофей решил сортировать таблицу результатов следующим образом: при сравнении двух участников выше будет идти тот, у которого решено больше задач. При равенстве числа решённых задач первым идёт участник с меньшим штрафом. Если же и штрафы совпадают, то первым будет тот, у которого логин идёт раньше в алфавитном (лексикографическом) порядке.
Тимофей заказал толстовки для победителей и накануне поехал за ними в магазин. В своё отсутствие он поручил вам реализовать алгоритм быстрой сортировки (англ. quick sort) для таблицы результатов. Так как Тимофей любит спортивное программирование и не любит зря расходовать оперативную память, то ваша реализация сортировки не может потреблять O(n) дополнительной памяти для промежуточных данных (такая модификация быстрой сортировки называется "in-place").
**Как работает in-place quick sort**
Как и в случае обычной быстрой сортировки, которая использует дополнительную память, необходимо выбрать опорный элемент (англ. pivot), а затем переупорядочить массив. Сделаем так, чтобы сначала шли элементы, не превосходящие опорного, а затем —– большие опорного.
Затем сортировка вызывается рекурсивно для двух полученных частей. Именно на этапе разделения элементов на группы в обычном алгоритме используется дополнительная память. Теперь разберёмся, как реализовать этот шаг in-place.
Пусть мы как-то выбрали опорный элемент. Заведём два указателя left и right, которые изначально будут указывать на левый и правый концы отрезка соответственно. Затем будем двигать левый указатель вправо до тех пор, пока он указывает на элемент, меньший опорного. Аналогично двигаем правый указатель влево, пока он стоит на элементе, превосходящем опорный. В итоге окажется, что что левее от left все элементы точно принадлежат первой группе, а правее от right — второй. Элементы, на которых стоят указатели, нарушают порядок. Поменяем их местами (в большинстве языков программирования используется функция swap()) и продвинем указатели на следующие элементы. Будем повторять это действие до тех пор, пока left и right не столкнутся.
На рисунке представлен пример разделения при pivot=5. Указатель left — голубой, right — оранжевый.
```
#### Формат ввода
```
В первой строке задано число участников n, 1 ≤ n ≤ 100 000.
В каждой из следующих n строк задана информация про одного из участников.
i-й участник описывается тремя параметрами:
 - уникальным логином (строкой из маленьких латинских букв длиной не более 20)
 - числом решённых задач Pi
 - штрафом Fi
Fi и Pi — целые числа, лежащие в диапазоне от 0 до 10^9.
```
#### Формат вывода
```
Для отсортированного списка участников выведите по порядку их логины по одному в строке.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        5<br>
        alla 4 100<br>
        gena 6 1000<br>
        gosha 2 90<br>
        rita 2 90<br>
        timofey 4 80<br>
    </td>
    <td valign="top">
        gena<br>
        timofey<br>
        alla<br>
        gosha<br>
        rita<br>
    </td>
  </tr>
</tbody></table>

</details>
